7.3 מיון-מהיר
(המשך)
מבנה
נתונים ואלגוריתמים
מיון-מהיר - העובדות
מיון-מהיר הוא
בדרך כלל אלגוריתם המיון הידוע הטוב ביותר, אך יש לו מגבלות רציניות, אשר
חייבים להבינם
לפני שעושים בו שימוש.
מה יקרה אם נפנה לשגרת ה- qsort מהדף הקודם עם מערך שהוא כבר ממוין? זהו מצב
שלגביו ניתן
לצפות כי הביצועים יהיו טובים יחסית!
אולם, הניסיון
הראשון לחלק את הבעיה לשתי תתי-בעיות יחזיר את החלק התחתון של החלוקה ריק - מאחר
שהפריט הראשון הוא הקטן ביותר. לכן החלוקה הראשונה פשוט תוריד פריט אחד ותקרא ל- qsort לחלוקה עם n-1
פריטים! דבר זה יקרה שוב n-2 פעמים נוספות! כל חלוקה דורשת O(n) פעולות - ויש לנו O(n) קריאות כאלה. לכן:
|
זהירות!! במקרה הגרוע ביותר, מיון-מהיר הוא אלגוריתם של O(n²)! |
כיצד ניתן
להתגבר על חסרון זה?
קיימות מספר
גרסאות המשנות את מיון-מהיר שבאופן כללי נותנות תוצאות טובות יותר: במקום לבחור את
הפריט הראשון כפריט הציר ננקטות אסטרטגיות אחרות.
בשיטה זו
נבחרים שלושה "מועמדים" לשמש כפריט ציר, והפריט שנבחר הוא זה האמצעי
בגודלו. אם המועמדים נבחרים מהמקומות הראשון, האמצעי והאחרון, אזי קל לראות כי
עבור מערך ממוין תתקבל תוצאה אופטימלית: כל חלוקה תחלק את הבעיה בדיוק לשניים
(פלוס/מינוס פריט אחד) ויהיה צורך בדיוק ב- ceiling(logn) קריאות רקורסיביות.
בשיטה זו של
בחירה אקראית של פריט הציר מושגת יעילות גם כשהקלט הינו מערך ממוין. במקרה כזה
הבחירה האקראית תגרום בממוצע לחלוקת הבעיה לשני חלקים שווים ותידרשנה O(logn) חלוקות.
|
בכל
אופן, בכל אסטרטגיה שבה נשתמש לבחירת פריט הציר, יהיה ניתן להציע מקרה שבו
הבעיה אינה מתחלקת באופן שווה בכל שלב של חלוקה. לכן יש להתייחס תמיד למיון-מהיר כבעל זמן מיון פוטנציאלי של O(n²). |
אז מדוע להתעסק
בכלל עם מיון-מהיר? מיון-ערמה הוא תמיד O(nlogn)!
המשך ל: השוואה
בין מיון מהיר למיון ערימה חזור
ל: תוכן עניינים